In this paper we present a new routing paradigm that generalizesopportunistic routing for wireless multihop networks. In multirate anypathrouting, each node uses both a set of next hops and a selected transmissionrate to reach a destination. Using this rate, a packet is broadcast to thenodes in the set and one of them forwards the packet on to the destination. Todate, there has been no theory capable of jointly optimizing both the set ofnext hops and the transmission rate used by each node. We solve this byintroducing two polynomial-time routing algorithms and provide the proof oftheir optimality. The proposed algorithms run in roughly the same running timeas regular shortest-path algorithms, and are therefore suitable for deploymentin routing protocols. We conducted measurements in an 802.11b testbed network,and our trace-driven analysis shows that multirate anypath routing performs onaverage 80% and up to 6.4 times better than anypath routing with a fixed rateof 11 Mbps. If the rate is fixed at 1 Mbps instead, performance improves by upto one order of magnitude.
展开▼
